Backtrack more aggressively when resolving
authorAlex Crichton <alex@alexcrichton.com>
Mon, 13 Jul 2015 19:14:05 +0000 (12:14 -0700)
committerAlex Crichton <alex@alexcrichton.com>
Fri, 17 Jul 2015 19:55:28 +0000 (12:55 -0700)
commit44eb16d3b13fb3916492f7e6a5d157101e13f39f
treebf83723edf307b29d451dd7b8c21e65ddc6d97ad
parentf3d6e35fbcc44e66b57f308a67d12a3a389918ac
Backtrack more aggressively when resolving

Resolving a dependency graph may involve quite a bit of backtracking to select
different versions of crates, but the previous implementation of resolution
would not backtrack enough.

Once a dependency is completely resolved it's possible that any number of
candidates for its transitive dependencies were left out of the resolution
process (e.g. we didn't hit them yet). These candidates were not previously used
for backtracking (because resolution overall of the dependency finished), but
this commit alters the implementation to instead consider these as candidates
for backtracking.

Architecturally this changes the code to CPS to pass around a `finished`
continuation to allow tweaking the behavior whenever a dependency successfully
resolves. The key change is then that whenever a candidate for a dependency is
activated, we ensure the recursive step for the rest of the graph happens as a
sub-call. This means that if *anything* in the recursive call fails (including
some previous up-the-stack resolution) we'll retry the next candidate.

Closes #1800
src/cargo/core/resolver/mod.rs
tests/resolve.rs